package com.darrenchan.leetcode;

import java.util.*;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-10-22 21:56
 */
public class Q332 {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> res = new ArrayList<>();
        Map<String, PriorityQueue<String>> map = new HashMap<>();

        int len = tickets.size();
        for (int i = 0; i < len; i++) {
            if(!map.containsKey(tickets.get(i).get(0))) {
                map.put(tickets.get(i).get(0), new PriorityQueue<String>());
            }

            map.get(tickets.get(i).get(0)).add(tickets.get(i).get(1));
        }

        String cur = "JFK";

        dfs(cur, map, res);

        return res;
    }

    private void dfs(String cur, Map<String, PriorityQueue<String>> map, List<String> res) {
        while (map.containsKey(cur) && !map.get(cur).isEmpty()) {
            dfs(map.get(cur).poll(), map, res);
        }

        res.add(0, cur);
    }
}
